package com.xcoder.algorithm.sort;

/**
 * 堆排序，选择排序的加强版
 * <p>
 * 思路：
 * 1.对数组原地建大顶堆(heapify)，利用自下而上的下滤
 * 2.循环执行以下操作，直到堆的元素数量为1
 * √ 交换堆顶元素与尾元素
 * √ 堆的元素数量减1
 * √ 对0位置进行1次下滤siftDown操作
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] a = {2, 1, 4, 0, 12, 32, 2, 9, 5, 3, 12, 14};
        heapSort(a);
        System.out.print("排序结果：");
        for (int i : a) {
            System.out.print(i + " ");
        }
    }

    private static void heapSort(int[] a) {
        if (a == null || a.length < 2) {
            return;
        }
        int len = a.length;
        // 1.原地建大顶堆，自下而上的下滤
        for (int i = (len >> 1) - 1; i >= 0; i--) {
            siftDown(a, len, i);
        }
        // 2.交换堆顶元素与尾元素，尾元素此时值最大，此时需要调整大顶堆，堆顶元素下滤
        for (int i = len - 1; i > 0; i--) {
            swap(a, 0, i);
            siftDown(a, i, 0);
        }
    }

    /**
     * 非递归
     */
    private static void siftDown(int[] a, int len, int index) {
        int element = a[index];
        int half = len >> 1;
        // 下滤的必须是非叶子节点
        while (index < half) {
            int li = (index << 1) + 1;
            int ri = li + 1;
            // 默认左子节点值最大
            int maxi = li;
            // 当前下滤的是父节点，一定有左子节点但是不一定有右子节点
            if (ri < len && a[ri] > a[li]) {
                maxi = ri;
            }
            // 如果父节点 >= 两个子节点的值，则无需交换
            if (element >= a[maxi]) {
                break;
            }
            a[index] = a[maxi];
            index = maxi;
        }
        a[index] = element;
    }

    private static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}


